package com.quickUnion;

import com.UF;

import java.util.Arrays;

public class QuickUnionByMySelf implements UF {

    private int[] id;

    private int count;

    public QuickUnionByMySelf(int count) {
        this.count = count;
        this.id = new int[count];
        for (int i = 0; i < this.id.length; i++) {
            this.id[i] = i;
        }
    }

    @Override
    public void union(int p, int q) {
        int rootContactPointP = this.getRootContactPoint(p);
        int rootContactPointQ = this.getRootContactPoint(q);

        int portionP = this.id[rootContactPointP];

//      把根触点p的分量修改为一个链接，这个链接指向q触点，q触点有自己的分量（相当于把触点p的分量合并到了触点q的分量，触点p的分量就消失了）
        this.id[rootContactPointP] = rootContactPointQ;
        this.count--;
        System.out.printf("已将原根触点【%d】的分量【%d】修改为链接，该链接指向触点【%d】，其分量是【%d】\n",rootContactPointP,portionP,rootContactPointQ,this.id[rootContactPointQ]);
    }

    @Override
    public int find(int p) {
        int rootContactPoint = getRootContactPoint(p);

        return this.id[rootContactPoint];

    }

    private int getRootContactPoint(int p) {
        int contactPoint = p; // 触点
        int link = this.id[contactPoint];// 链接（这个触点的链接最终将指向根，根就是这个触点所在的分量）

        while (contactPoint != link) {
//            在循环中，说明当前这个触点不是根节点（数组中该触点的值是一个指向根节点的链接）
            contactPoint = this.id[link];  // 通过上一个触点的链接定位到下一个触点
            link = this.id[contactPoint];  // 获得该触点的值,这个值有可能是链接、也有可能是值，等待while的条件判断
        }
        //        跳出while循环，说明这个当前触点是一个根触点，此时的link代表的不再是link，而是分量
        return contactPoint;
    }

    @Override
    public boolean connected(int p, int q) {

        return this.find(p) == this.find(q);
    }

    @Override
    public int count() {
        System.out.println(Arrays.toString(this.id));
        return this.count;
    }
}
